/*
 * @lc app=leetcode.cn id=39 lang=javascript
 *
 * [39] 组合总和
 */

// @lc code=start
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
 var combinationSum = function(candidates, target) {
  let res = []
  const dfs = (start, list, value) => {
    if (value > target) {
      return;
    }
    if (value === target) {
      return res.push(list.slice())
    }
    for (let i = start; i <candidates.length; i++) {
      value += candidates[i]
      list.push(candidates[i])
      dfs(i, list, value)
      // 回溯
      value -= candidates[i]
      list.pop()
    }
  }
  dfs(0, [], 0)
  return res
};
// @lc code=end
// var combinationSum = function(candidates, target) {
//   let res = []
//   const dfs = (index, list, value) => {
//     if (index === candidates.length) return
//     if (value === 0) {
//       return res.push(list)
//     }
//     // 直接跳过
//     dfs(index+1, list, value)
//     // 选择当前的数
//     if (value - candidates[index] >= 0) {
//       dfs(index, [...list, candidates[index]], value - candidates[index])
//     }
//   }
//   dfs(0, [], target)
//   return res
// };